Білоруський державний університет інформатики і радіоелектроніки
Кафедра РЕЗ
Реферат на тему:
«Коди без пам'яті. Коди Хаффмена. Коди з пам'яттю »
МІНСЬК, 2009
Коди без пам'яті. Коди Хаффмена
Найпростішими кодами, на основі яких може виконуватися стиснення даних, є коди без пам'яті. У коді без пам'яті кожен символ в кодованої векторі даних замінюється кодовим словом з префіксного безлічі двійкових послідовностей або слів.
Префіксним безліччю двійкових послідовностей S називається скінченна множина двійкових послідовностей, таких, що жодна послідовність у цій множині не є префіксом, або початком, ніякої іншої послідовності в S.
Наприклад, безліч двійкових слів S1 = {00, 01, 100, 110, 1010, 1011} є префіксним безліччю двійкових послідовностей, оскільки, якщо перевірити будь-яку з 30 можливих спільних комбінацій (w i w j) з S1, то видно, що w i ніколи не з'явиться префіксом (або початком) w j. З іншого боку, безліч S2 = {00, 001, 1110} не є префіксним безліччю двійкових послідовностей, так як послідовність 00 є префіксом (початком) іншій послідовності з цієї множини - 001.
Таким чином, якщо необхідно закодувати деякий вектор даних X = (X 1, x 2, ... x n) з алфавітом даних A розміру k, то кодування кодом без пам'яті здійснюється наступним чином:
- Складають повний список символів a 1, a 2, a j ... , A k алфавіту A , В якому a j - j-й за частотою появи в X символ, тобто першим в списку буде стояти найбільш часто зустрічається в алфавіті символ, другим - рідше зустрічається і т.д.;
- Кожному символу a j призначають кодове слово w j з префіксного безлічі двійкових послідовностей S;
- Вихід кодера отримують об'єднанням в одну послідовність всіх отриманих двійкових слів.
Формування префіксних множин і робота з ними - це окрема серйозна тема з теорії множин, що виходить за рамки нашого курсу, але кілька необхідних зауважень все-таки доведеться зробити.
Якщо S = {w 1, w 2, ... , W k} - Префіксне множина, то можна визначити деякий вектор v (S) = (L 1, L 2, ..., L k), що складається з чисел, які є довжинами відповідних префіксних послідовностей (L i - довжина w i) .
Вектор (L 1, L 2, ..., L k), що складається з неуменьшающимся позитивних цілих чисел, називається вектором Крафта. Для нього виконується нерівність
Це нерівність називається нерівністю Крафта. Для нього справедливо наступне твердження: якщо S - яке-небудь Префіксне безліч, то v (S) - вектор Крафта.
Іншими словами, довжини двійкових послідовностей в префіксним безлічі задовольняють нерівності Крафта.
Якщо нерівність (1) переходить у сувору рівність, то такий код називається компактним і володіє найменшою серед кодів з даними алфавітом довжиною, тобто є оптимальним.
Нижче наведені приклади найпростіших префіксних множин та відповідні їм вектори Крафта:
S1 = {0, 10, 11} і v (S1) = (1, 2, 2);
S2 = {0, 10, 110, 111} і v (S2) = (1, 2, 3, 3);
S3 = {0, 10, 110, 1110, 1111} і v (S3) = (1, 2, 3, 4, 4);
S4 = {0, 10, 1100, 1101, 1110, 1111} і v (S4) = (1, два, 4, 4, 4, 4);
S5 = {0, 10, 1100, 1101, 1110, 11110, 11111} і v (S5) = (1, 2, 4, 4, 4, 5, 5);
S6 = {0, 10, 1100, 1101, 1110, 11110, 111110, 111111}
і v (S 6) = (1,2,4,4,4,5,6,6).
Припустимо ми хочемо розробити код без пам'яті для стиснення вектора даних X = (x 1, x 2, ... x n) з алфавітом A розміром в k символів. Введемо в розгляд так званий вектор частот F = (F 1, F 2, ..., F k), де F i - кількість появ i-го найбільш часто зустрічається символу з A в X. Закодуємо X кодом без пам'яті, для якого вектор Крафта L = (L 1, L 2, ..., L k).
Тоді довжина двійкової кодової послідовності B (X) на виході кодера складе
L * F = L 1 * F 1 + L 2 * F 2 + ... + L k * F k. (2)
Кращим кодом без пам'яті був би код, для якого довжина B (X) - мінімальна. Для розробки такого коду нам потрібно знайти вектор Крафта L, для якого твір L * F було б мінімальним.
Простий перебір можливих варіантів - взагалі-то, не найкращий спосіб знайти такий вектор Крафта, особливо для великого k.
Алгоритм Хаффмена, названий на честь його винахідника - Девіда Хаффмена, - дає нам ефективний спосіб пошуку оптимального вектора Крафта L для F, тобто такого L, для якого точкове твір L * F - мінімально. Код, отриманий з використанням оптимального L для F, називають кодом Хаффмена.
Недоліки методу Хаффмена
Найбільшою складністю з кодами Хаффмена, як випливає з попереднього обговорення, є необхідність мати таблиці ймовірностей для кожного типу стисливих даних. Це не є проблемою, якщо відомо, що стискається англійська чи російський текст, ми просто надаємо кодеру і декодеру підходяще для англійської або російської тексту кодове дерево. У загальному ж випадку, коли ймовірність символів для вхідних даних невідома, статичні коди Хаффмена працюють неефективно.
Вирішенням цієї проблеми є статистичний аналіз кодованих даних, що виконується в ході першого проходу за даними, і складання на його основі кодового дерева. Власне кодування при цьому виконується друга проходом.
Існує, правда, динамічна версія стиснення Хаффмена, яка може будувати дерево Хаффмена "на льоту" під час читання та активного стиснення. Дерево постійно оновлюється, щоб відображати зміни ймовірностей вхідних даних. Проте і вона на практиці володіє серйозними обмеженнями та недоліками і, крім того, забезпечує меншу ефективність стиснення.
Ще один недолік кодів Хаффмена - це те, що мінімальна довжина кодового слова для них не може бути менше одиниці, тоді як ентропія повідомлення цілком може складати і 0,1, і 0,01 біт / літеру. У цьому випадку код Хаффмена стає істотно надлишковим. Проблема вирішується застосуванням алгоритму до блоків символів, але тоді ускладнюється процедура кодування / декодування і значно розширюється кодове дерево, яке потрібно в кінцевому підсумку зберігати разом з кодом.
Нарешті, код Хаффмена забезпечує середню довжину коду, збігається з ентропією, тільки в тому випадку, коли ймовірності символів джерела є цілими негативними ступенями двійки: 1 / 2 = 0,5; 1 / 4 = 0,25; 1 / 8 = 0,125; 1 / 16 = 0,0625 і т.д. На практиці ж така ситуація зустрічається дуже рідко або може бути створена блокуванням символів з усіма наслідками, що випливають звідси наслідками.
Коди з пам'яттю
Зазвичай розглядають два типи кодів з пам'яттю:
- Блочні коди;
- Коди з кінцевою пам'яттю.
Блочний код ділить вектор даних на блоки заданої довжини і потім кожен блок замінюють кодовим словом з префіксного безлічі двійкових слів. Отриману послідовність кодових слів об'єднують в результуючу двійкову рядок на виході кодера. Про блочному коді говорять, що він - блочний код k-го порядку, якщо всі блоки мають довжину, рівну k.
Як приклад стиснемо вектор даних X = (0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1), використовуючи блочний код другого порядку.
Спочатку розіб'ємо вектор X на блоки довжини 2: 01, 10, 10, 01, 11, 10, 01, 01.
Будемо розглядати ці блоки як елементи нового "гіпералфавіта" {01, 10, 11}. Щоб визначити, який код призначити якого їх символів цього нового алфавіту, визначимо вектор частот появ елементів додаткового алфавіту в послідовності блоків. Отримаємо вектор частот (4, 3, 1), тобто найбільш часто зустрічається блок 01 з'являється 4 рази, наступний за частотою зустрічальності блок 10 - три рази і найменш часто зустрічається блок 11 - лише один раз.
Оптимальний вектор Крафта для вектора частот (4, 3, 1) - це вектор (1, 2, 2). Таким чином, кодер для оптимального блокового коду другого порядку стосовно заданому вектору даних X визначається табл. 1.
Таблиця 1
Замінюючи кожен блок присвоєним йому кодовим словом з таблиці кодера, отримаємо послідовність кодових слів:
0, 10, 10, 0, 11, 10, 0, 0.
Об'єднуючи ці кодові слова разом, маємо вихідну послідовність кодера:
B (X) = (0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0).
Можна перевірити, що ентропія H (X) вихідного вектора X дорівнює 0.9887 біт / букву, а ступінь стиснення, що отримується в результаті використання блокового коду R (X) = 12/16 = 0.75 біт на вибірку даних, виявилася меншою нижньої межі ентропії. Отриманий результат, здавалося б, суперечить теоремі Шеннона, яка каже, що неможливо досягти середньої довжини коду, меншою ентропії джерела. Однак насправді це не так. Якщо уважно подивитися на вектор даних X, то можна помітити закономірність: за символом 0 частіше варто 1, тобто умовна ймовірність Р (1 / 0) значно більше, ніж просто Р (0). Отже, ентропію цього джерела треба вважати як ентропію складного повідомлення, а вона, як відомо, завжди менше, ніж для джерела простих повідомлень.
Код з кінцевою пам'яттю при кодуванні вектора даних (X 1, X 2, ..., X n) використовує кодову книгу, що складається з декількох різних кодів без пам'яті. Кожна вибірка даних кодується кодом без пам'яті з кодової книги, визначеним значенням деякого числа попередніх вибірок даних.
Як приклад кодування кодом з пам'яттю розглянемо вже згадуваний раніше класичний приклад X = ABRACADABRA. У цій послідовності абсолютно очевидна сильна статистична залежність між її черговими символами, яка повинна обов'язково враховуватися при виборі методу кодування.
Кодер з пам'яттю при кодуванні поточного символу враховує значення попереднього йому символу. Таким чином, кодове слово для поточного символу A буде різним у поєднаннях RA, DA і CA (іншими словами, код має пам'ять в один символ джерела) (табл. 2).
Таблиця 2
Результат кодування - вектор B (X) = (10111011111011) довжиною в 11 біт і швидкістю стиснення R = 13/11 = 1,18 біта на символ даних, тоді як при кодуванні рівномірним трехразрядного кодом з R = 3 знадобилося б 33 біта.
ЛІТЕРАТУРА
1. Лідовскій В.І. Теорія інформації. - М., «Вища школа», 2002р. - 120с.
2. Метрологія та радіовимірювань в телекомунікаційних системах. Підручник для ВУЗів. / В. І. Нефедов, В. І. Халкин, Є. В. Федоров та ін - М.: Вища школа, 2001 р . - 383с.
3. Цапенко М.П. Вимірювальні інформаційні системи. - М.: Енергоатом издат, 2005. - 440С.
4. Зюко А.Г. , Кловський Д.Д., Назаров М.В., Фінк Л.М. Теорія передачі сигналів. М: Радіо і зв'язок, 2001 р . -368 С.
5. Б. Скляр. Цифрова зв'язок. Теоретичні основи та практичне застосування. Вид. 2-е, испр.: Пер. з англ. - М.: Видавничий дім «Вільямс», 2003 р . - 1104 с.
Кафедра РЕЗ
Реферат на тему:
«Коди без пам'яті. Коди Хаффмена. Коди з пам'яттю »
МІНСЬК, 2009
Коди без пам'яті. Коди Хаффмена
Найпростішими кодами, на основі яких може виконуватися стиснення даних, є коди без пам'яті. У коді без пам'яті кожен символ в кодованої векторі даних замінюється кодовим словом з префіксного безлічі двійкових послідовностей або слів.
Префіксним безліччю двійкових послідовностей S називається скінченна множина двійкових послідовностей, таких, що жодна послідовність у цій множині не є префіксом, або початком, ніякої іншої послідовності в S.
Наприклад, безліч двійкових слів S1 = {00, 01, 100, 110, 1010, 1011} є префіксним безліччю двійкових послідовностей, оскільки, якщо перевірити будь-яку з 30 можливих спільних комбінацій (w i w j) з S1, то видно, що w i ніколи не з'явиться префіксом (або початком) w j. З іншого боку, безліч S2 = {00, 001, 1110} не є префіксним безліччю двійкових послідовностей, так як послідовність 00 є префіксом (початком) іншій послідовності з цієї множини - 001.
Таким чином, якщо необхідно закодувати деякий вектор даних X = (X 1, x 2, ... x n) з алфавітом даних A розміру k, то кодування кодом без пам'яті здійснюється наступним чином:
- Складають повний список символів a 1, a 2, a j ... , A k алфавіту A , В якому a j - j-й за частотою появи в X символ, тобто першим в списку буде стояти найбільш часто зустрічається в алфавіті символ, другим - рідше зустрічається і т.д.;
- Кожному символу a j призначають кодове слово w j з префіксного безлічі двійкових послідовностей S;
- Вихід кодера отримують об'єднанням в одну послідовність всіх отриманих двійкових слів.
Формування префіксних множин і робота з ними - це окрема серйозна тема з теорії множин, що виходить за рамки нашого курсу, але кілька необхідних зауважень все-таки доведеться зробити.
Якщо S = {w 1, w 2, ... , W k} - Префіксне множина, то можна визначити деякий вектор v (S) = (L 1, L 2, ..., L k), що складається з чисел, які є довжинами відповідних префіксних послідовностей (L i - довжина w i) .
Вектор (L 1, L 2, ..., L k), що складається з неуменьшающимся позитивних цілих чисел, називається вектором Крафта. Для нього виконується нерівність
Це нерівність називається нерівністю Крафта. Для нього справедливо наступне твердження: якщо S - яке-небудь Префіксне безліч, то v (S) - вектор Крафта.
Іншими словами, довжини двійкових послідовностей в префіксним безлічі задовольняють нерівності Крафта.
Якщо нерівність (1) переходить у сувору рівність, то такий код називається компактним і володіє найменшою серед кодів з даними алфавітом довжиною, тобто є оптимальним.
Нижче наведені приклади найпростіших префіксних множин та відповідні їм вектори Крафта:
S1 = {0, 10, 11} і v (S1) = (1, 2, 2);
S2 = {0, 10, 110, 111} і v (S2) = (1, 2, 3, 3);
S3 = {0, 10, 110, 1110, 1111} і v (S3) = (1, 2, 3, 4, 4);
S4 = {0, 10, 1100, 1101, 1110, 1111} і v (S4) = (1, два, 4, 4, 4, 4);
S5 = {0, 10, 1100, 1101, 1110, 11110, 11111} і v (S5) = (1, 2, 4, 4, 4, 5, 5);
S6 = {0, 10, 1100, 1101, 1110, 11110, 111110, 111111}
і v (S 6) = (1,2,4,4,4,5,6,6).
Припустимо ми хочемо розробити код без пам'яті для стиснення вектора даних X = (x 1, x 2, ... x n) з алфавітом A розміром в k символів. Введемо в розгляд так званий вектор частот F = (F 1, F 2, ..., F k), де F i - кількість появ i-го найбільш часто зустрічається символу з A в X. Закодуємо X кодом без пам'яті, для якого вектор Крафта L = (L 1, L 2, ..., L k).
Тоді довжина двійкової кодової послідовності B (X) на виході кодера складе
L * F = L 1 * F 1 + L 2 * F 2 + ... + L k * F k. (2)
Кращим кодом без пам'яті був би код, для якого довжина B (X) - мінімальна. Для розробки такого коду нам потрібно знайти вектор Крафта L, для якого твір L * F було б мінімальним.
Простий перебір можливих варіантів - взагалі-то, не найкращий спосіб знайти такий вектор Крафта, особливо для великого k.
Алгоритм Хаффмена, названий на честь його винахідника - Девіда Хаффмена, - дає нам ефективний спосіб пошуку оптимального вектора Крафта L для F, тобто такого L, для якого точкове твір L * F - мінімально. Код, отриманий з використанням оптимального L для F, називають кодом Хаффмена.
Алгоритм Хаффмена
Алгоритм Хаффмена витончено реалізує загальну ідею статистичного кодування з використанням префіксних множин і працює наступним чином:
1. Виписуємо в ряд всі символи алфавіту в порядку зростання або убування ймовірності їхньої появи в тексті.
2. Послідовно об'єднуємо два символи з найменшими ймовірностями появи в новий складовою символ, імовірність появи якого вважаємо рівній сумі ймовірностей складових його символів. Врешті-решт побудуємо дерево, кожен вузол якого має сумарну ймовірність всіх вузлів, що знаходяться нижче нього.
3. Простежуємо шлях до кожного листа дерева, позначаючи напрямок до кожного вузла (наприклад, направо - 1, наліво - 0). Отримана послідовність дає кодове слово, відповідне кожному символу (мал. 1).
Побудуємо кодове дерево для повідомлення з наступним абеткою:
A B C D E
10 5 8 13 10
B C A E D
5 8 10 10 13
A E BC D
10 10 13 13
BC D AE
13 13 20
AE BCD
20 26
AEBCD
0 |
1 |
C |
B |
0 |
0 |
0 |
1 |
1 |
1 |
E |
A |
D |
46
Рис. 1 Недоліки методу Хаффмена
Найбільшою складністю з кодами Хаффмена, як випливає з попереднього обговорення, є необхідність мати таблиці ймовірностей для кожного типу стисливих даних. Це не є проблемою, якщо відомо, що стискається англійська чи російський текст, ми просто надаємо кодеру і декодеру підходяще для англійської або російської тексту кодове дерево. У загальному ж випадку, коли ймовірність символів для вхідних даних невідома, статичні коди Хаффмена працюють неефективно.
Вирішенням цієї проблеми є статистичний аналіз кодованих даних, що виконується в ході першого проходу за даними, і складання на його основі кодового дерева. Власне кодування при цьому виконується друга проходом.
Існує, правда, динамічна версія стиснення Хаффмена, яка може будувати дерево Хаффмена "на льоту" під час читання та активного стиснення. Дерево постійно оновлюється, щоб відображати зміни ймовірностей вхідних даних. Проте і вона на практиці володіє серйозними обмеженнями та недоліками і, крім того, забезпечує меншу ефективність стиснення.
Ще один недолік кодів Хаффмена - це те, що мінімальна довжина кодового слова для них не може бути менше одиниці, тоді як ентропія повідомлення цілком може складати і 0,1, і 0,01 біт / літеру. У цьому випадку код Хаффмена стає істотно надлишковим. Проблема вирішується застосуванням алгоритму до блоків символів, але тоді ускладнюється процедура кодування / декодування і значно розширюється кодове дерево, яке потрібно в кінцевому підсумку зберігати разом з кодом.
Нарешті, код Хаффмена забезпечує середню довжину коду, збігається з ентропією, тільки в тому випадку, коли ймовірності символів джерела є цілими негативними ступенями двійки: 1 / 2 = 0,5; 1 / 4 = 0,25; 1 / 8 = 0,125; 1 / 16 = 0,0625 і т.д. На практиці ж така ситуація зустрічається дуже рідко або може бути створена блокуванням символів з усіма наслідками, що випливають звідси наслідками.
Коди з пам'яттю
Зазвичай розглядають два типи кодів з пам'яттю:
- Блочні коди;
- Коди з кінцевою пам'яттю.
Блочний код ділить вектор даних на блоки заданої довжини і потім кожен блок замінюють кодовим словом з префіксного безлічі двійкових слів. Отриману послідовність кодових слів об'єднують в результуючу двійкову рядок на виході кодера. Про блочному коді говорять, що він - блочний код k-го порядку, якщо всі блоки мають довжину, рівну k.
Як приклад стиснемо вектор даних X = (0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1), використовуючи блочний код другого порядку.
Спочатку розіб'ємо вектор X на блоки довжини 2: 01, 10, 10, 01, 11, 10, 01, 01.
Будемо розглядати ці блоки як елементи нового "гіпералфавіта" {01, 10, 11}. Щоб визначити, який код призначити якого їх символів цього нового алфавіту, визначимо вектор частот появ елементів додаткового алфавіту в послідовності блоків. Отримаємо вектор частот (4, 3, 1), тобто найбільш часто зустрічається блок 01 з'являється 4 рази, наступний за частотою зустрічальності блок 10 - три рази і найменш часто зустрічається блок 11 - лише один раз.
Оптимальний вектор Крафта для вектора частот (4, 3, 1) - це вектор (1, 2, 2). Таким чином, кодер для оптимального блокового коду другого порядку стосовно заданому вектору даних X визначається табл. 1.
Таблиця 1
| Таблиця кодера | |
| Блок | Кодове слово |
| 01 | 0 |
| 10 | 10 |
| 11 | 11 |
0, 10, 10, 0, 11, 10, 0, 0.
Об'єднуючи ці кодові слова разом, маємо вихідну послідовність кодера:
B (X) = (0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0).
Можна перевірити, що ентропія H (X) вихідного вектора X дорівнює 0.9887 біт / букву, а ступінь стиснення, що отримується в результаті використання блокового коду R (X) = 12/16 = 0.75 біт на вибірку даних, виявилася меншою нижньої межі ентропії. Отриманий результат, здавалося б, суперечить теоремі Шеннона, яка каже, що неможливо досягти середньої довжини коду, меншою ентропії джерела. Однак насправді це не так. Якщо уважно подивитися на вектор даних X, то можна помітити закономірність: за символом 0 частіше варто 1, тобто умовна ймовірність Р (1 / 0) значно більше, ніж просто Р (0). Отже, ентропію цього джерела треба вважати як ентропію складного повідомлення, а вона, як відомо, завжди менше, ніж для джерела простих повідомлень.
Код з кінцевою пам'яттю при кодуванні вектора даних (X 1, X 2, ..., X n) використовує кодову книгу, що складається з декількох різних кодів без пам'яті. Кожна вибірка даних кодується кодом без пам'яті з кодової книги, визначеним значенням деякого числа попередніх вибірок даних.
Як приклад кодування кодом з пам'яттю розглянемо вже згадуваний раніше класичний приклад X = ABRACADABRA. У цій послідовності абсолютно очевидна сильна статистична залежність між її черговими символами, яка повинна обов'язково враховуватися при виборі методу кодування.
Кодер з пам'яттю при кодуванні поточного символу враховує значення попереднього йому символу. Таким чином, кодове слово для поточного символу A буде різним у поєднаннях RA, DA і CA (іншими словами, код має пам'ять в один символ джерела) (табл. 2).
Таблиця 2
| Кодер | |
| Символ, попередній символ | Кодове слово |
| (A, -) | 1 |
| (B, A) | 0 |
| (C, A) | 10 |
| (D, A) | 11 |
| (A, R) | 1 |
| (R, B) | 1 |
| (A, C) | 1 |
| (A, B) | 1 |
ЛІТЕРАТУРА
1. Лідовскій В.І. Теорія інформації. - М., «Вища школа», 2002р. - 120с.
2. Метрологія та радіовимірювань в телекомунікаційних системах. Підручник для ВУЗів. / В. І. Нефедов, В. І. Халкин, Є. В. Федоров та ін - М.: Вища школа,
3. Цапенко М.П. Вимірювальні інформаційні системи. - М.: Енергоатом издат, 2005. - 440С.
4. Зюко А.Г. , Кловський Д.Д., Назаров М.В., Фінк Л.М. Теорія передачі сигналів. М: Радіо і зв'язок,
5. Б. Скляр. Цифрова зв'язок. Теоретичні основи та практичне застосування. Вид. 2-е, испр.: Пер. з англ. - М.: Видавничий дім «Вільямс»,